import java.util.*;

public class Solution {
    public int compareVersion(String version1, String version2) {
        int len1 = version1.length();
        int len2 = version2.length();
        int i = 0;
        int j = 0;
        while (i < len1 || j < len2) {
            int num1 = 0;
            while (i < len1 && version1.charAt(i) != '.') {
                num1 = num1 * 10 + version1.charAt(i) - '0';
                i++;
            }
            int num2 = 0;
            while (j < len2 && version2.charAt(j) != '.') {
                num2 = num2 * 10 + version2.charAt(j) - '0';
                j++;
            }
            if (num1 != num2) {
                return num1 > num2 ? 1 : -1;
            }
            i++;
            j++;
        }
        return 0;
    }

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - 1;
        while (right - left >= k) {
            if (Math.abs(arr[right] - x) >= Math.abs(arr[left] - x)) {
                right--;
            } else {
                left++;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            list.add(arr[i]);
        }
        Collections.sort(list);
        return list;
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> hashMap = new HashMap<>();
        for (String s : words) {
            if (hashMap.get(s) == null) {
                hashMap.put(s, 1);
            }
            hashMap.put(s, hashMap.get(s) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.add(entry);
                } else {
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.add(entry);
                        }
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            list.add(key);
        }
        Collections.reverse(list);
        return list;
    }

    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> hashMap = new HashMap<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch1 = s.charAt(i);
            char ch2 = t.charAt(i);
            if (hashMap.containsKey(ch1) && hashMap.get(ch1) != ch2 || !(hashMap.containsKey(ch1)) && hashMap.containsValue(ch2)) {
                return false;
            }
            hashMap.put(ch1, ch2);
        }
        return true;
    }

    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (Integer x : nums1) {
            if (hashMap.get(x) == null) {
                hashMap.put(x, 1);
            } else {
                hashMap.put(x, hashMap.get(x) + 1);
            }
        }
        int[] ret = new int[nums1.length];
        int index = 0;
        for (Integer y : nums2) {
            if (hashMap.containsKey(y) && hashMap.get(y) > 0 && index < ret.length) {
                int count = hashMap.get(y);
                ret[index++] = y;
                hashMap.put(y, --count);
            }
        }
        ret = Arrays.copyOfRange(ret, 0, index);
        return ret;
    }

    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> hashSet = new HashSet<>();
        for (Integer x : nums1) {
            hashSet.add(x);
        }
        int[] ret = new int[nums1.length];
        int index = 0;
        Set<Integer> hashSet2 = new HashSet<>();
        for (Integer y : nums2) {
            if (hashSet.contains(y) && index < nums1.length) {
                hashSet2.add(y);
            }
        }
        for (Integer z : hashSet2) {
            ret[index++] = z;
        }
        ret = Arrays.copyOfRange(ret, 0, index);
        return ret;
    }

    public int firstUniqChar(String s) {
        Map<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (hashMap.get(ch) == null) {
                hashMap.put(ch, 1);
            } else {
                hashMap.put(ch, hashMap.get(ch) + 1);
            }
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (hashMap.get(ch) == 1) {
                return i;
            }
        }
        return -1;
    }

    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    };
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer,Employee> hashMap = new HashMap<>();
        for (Employee x: employees) {
            hashMap.put(x.id,x);
        }
        return dfs(hashMap,id);
    }
    private int dfs(Map<Integer,Employee> hashMap, int id) {
        int sum = hashMap.get(id).importance;
        List<Integer> subordinates = hashMap.get(id).subordinates;
        for (Integer i: subordinates) {
            sum = sum + dfs(hashMap,i);
        }
        return sum;
    }

}